#include <vector>

//只出现一次的数字I
using namespace std;

class Solution {
public:
    int singleNumber(vector<int>& nums)
    {
        int res = 0;
        for (auto& e : nums)
        {
            res ^= e;
        }
        return res;
    }
};



//只出现一次的数字II
class Solution {
public:

    //思路 用二进制 一位一位的判断
    //如果某一位出现的次数不是0 或者3 或者3的倍数
    //如果是1或者4或者7或者3n+1 则需要返回的数字在这一位的二进制数就为1
    int singleNumber2(vector<int>& nums)
    {
        int res = 0;
        //遍历每一位二进制位
        for (int i = 0; i < 32; i++)
        {
            int count = 0;//统计出现的次数
            for (auto& e : nums)
            {
                count += ((e >> i) & 1);
            }
            if (count % 3)
            {
                res |= (1 << i);
            }
        }
        return res;
    }
};


//只出现一次的数字III
class Solution {
public:
    vector<int> singleNumber3(vector<int>& nums)
    {
        int tmp = 0;
        for (auto& e : nums)
        {
            tmp ^= e;
        }
        //tmp就是这两个答案异或之后的结果 根据这个结果将大数组分为两类
        //找到tmp里面最低位不为0的位数
        int flag = 0;
        for (int i = 0; i < 32; i++)
        {
            if ((tmp >> i) & 1)
            {
                flag = (1 << i);
                break;
            }
        }
        int num1 = 0, num2 = 0;
        for (auto& e : nums)
        {
            if (e & flag)
            {
                num1 ^= e;
            }
            else
            {
                num2 ^= e;
            }
        }
        return vector<int>{num1, num2};
    }
};
